package code.oldCode.classic150;

import utils.Node;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2025/1/9
 */
public class Classic150_graph {
    /* 200. 岛屿数量 */
    public int numIslands(char[][] grid) {
        int x = grid.length;
        int y = grid[0].length;
        int numIsland = 0;
        boolean[][] isVisited = new boolean[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!isVisited[i][j] && grid[i][j] == '1') {
                    numIsland++;
                    fillIsland(i, j, x, y, isVisited, grid);
                }
            }
        }
        return numIsland;
    }

    private void fillIsland(int i, int j, int x, int y, boolean[][] isVisited, char[][] grid) {
        isVisited[i][j] = true;
        // 找上下左右
        if (i - 1 >= 0 && !isVisited[i - 1][j] && grid[i][j] == '1')
            fillIsland(i - 1, j, x, y, isVisited, grid);
        if (i + 1 < x && !isVisited[i + 1][j] && grid[i][j] == '1')
            fillIsland(i + 1, j, x, y, isVisited, grid);
        if (j - 1 >= 0 && !isVisited[i][j - 1] && grid[i][j] == '1')
            fillIsland(i, j - 1, x, y, isVisited, grid);
        if (j + 1 < y && !isVisited[i][j + 1] && grid[i][j] == '1')
            fillIsland(i, j + 1, x, y, isVisited, grid);
    }

    /* 130. 被围绕的区域 */
    public void solve(char[][] board) {
        // ["O","O","O"]
        // ["O","O","O"]
        // ["O","O","O"]
        int m = board.length, n = board[0].length;
        // 1. 先遍历最外面的一圈，遍历到 O 就DFS把所有的 O 换为 -
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (0 < i && i < m - 1 && 0 < j && j < n - 1)
                    continue;
                if (board[i][j] == 'O')
                    setEdgeO(i, j, m, n, board);
            }
        }
        // 2. 遍历全部，把所有 O 换为 X ， 把所有 - 换为 O
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '-')
                    board[i][j] = 'O';
            }
        }
    }

    private void setEdgeO(int i, int j, int m, int n, char[][] board) {
        board[i][j] = '-';
        // 找上下左右
        if (i - 1 >= 0 && board[i - 1][j] == 'O')
            setEdgeO(i - 1, j, m, n, board);
        if (i + 1 < m && board[i + 1][j] == 'O')
            setEdgeO(i + 1, j, m, n, board);
        if (j - 1 >= 0 && board[i][j - 1] == 'O')
            setEdgeO(i, j - 1, m, n, board);
        if (j + 1 < n && board[i][j + 1] == 'O')
            setEdgeO(i, j + 1, m, n, board);
    }

    /* 133. 克隆图-自己的写法，略显麻烦 */
    public Node cloneGraph_mine(Node node) {
        if (node == null)
            return null;
        Map<Integer, Node> newMap = new HashMap<>();
        Map<Integer, Boolean> isVisited = new HashMap<>();
        fillMap(node, newMap); // 填充map，初始化所有的新Node
        Node newNode = newMap.get(node.val);
        connectNodes(node, newNode, isVisited, newMap); // 连接所有的新Node
        return newNode;
    }

    private void fillMap(Node node, Map<Integer, Node> newMap) {
        newMap.put(node.val, new Node(node.val));
        for (Node neighbor : node.neighbors) {
            if (!newMap.containsKey(neighbor.val))
                fillMap(neighbor, newMap);
        }
    }

    private void connectNodes(Node node, Node newNode, Map<Integer, Boolean> isVisited, Map<Integer, Node> newMap) {
        isVisited.put(node.val, true);
        for (Node neighbor : node.neighbors) {
            Node newNodeNeighbor = newMap.get(neighbor.val);
            newNode.neighbors.add(newNodeNeighbor);
            if (!isVisited.containsKey(neighbor.val)) {
                connectNodes(neighbor, newNodeNeighbor, isVisited, newMap);
            }
        }
    }

    /* 133. 克隆图-DFS写法 */
    public Map<Node, Node> map = new HashMap<>();
    public Node cloneGraph_DFS(Node node) {
        if (node == null)
            return null;

        if (map.containsKey(node))
            return map.get(node);

        Node copyNode = new Node(node.val);
        map.put(node, copyNode);
        for (Node neighbor : node.neighbors) {
            copyNode.neighbors.add(cloneGraph_DFS(neighbor));
        }

        return copyNode;
    }

    /* 133. 克隆图-BFS写法 */
    public Node cloneGraph_BFS(Node node) {
        if (node == null)
            return null;

        Deque<Node> deque = new ArrayDeque<>();
        Map<Node, Node> visited = new HashMap<>();

        deque.addFirst(node);
        Node copyNode = new Node(node.val);
        visited.put(node, copyNode);

        while (!deque.isEmpty()) {
            Node nowNode = deque.pollLast();
            for (Node neighbor : nowNode.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new Node(neighbor.val));
                    deque.addFirst(neighbor);
                }
                visited.get(nowNode).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }

    /* 399. 除法求值——你管着叫mid?
    *   好强啊这个题，学到了
    */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationsSize = equations.size();

        UnionFind unionFind = new UnionFind(2 * equationsSize);
        // 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
        Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize);
        int id = 0;
        for (int i = 0; i < equationsSize; i++) {
            List<String> equation = equations.get(i);
            String var1 = equation.get(0);
            String var2 = equation.get(1);

            if (!hashMap.containsKey(var1)) {
                hashMap.put(var1, id);
                id++;
            }
            if (!hashMap.containsKey(var2)) {
                hashMap.put(var2, id);
                id++;
            }
            unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
        }

        // 第 2 步：做查询
        int queriesSize = queries.size();
        double[] res = new double[queriesSize];
        for (int i = 0; i < queriesSize; i++) {
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);

            Integer id1 = hashMap.get(var1);
            Integer id2 = hashMap.get(var2);

            if (id1 == null || id2 == null) {
                res[i] = -1.0d;
            } else {
                res[i] = unionFind.isConnected(id1, id2);
            }
        }
        return res;
    }

    // 并查集
    private class UnionFind {
        private int[] parent;
        private double[] weight; // 指向的父结点的权值

        public UnionFind(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }

        /**
            ∵ x / y = value
            y / rootY = weight[y]
            ∵ x / rootX = weight[x]
            rootX / rootY = weight[rootX]
            ∴ value * weight[y] == weight[x] * weight[rootX]
         */
        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            parent[rootX] = rootY;
            // ※ 关系式的推导请见上方的公式 ※
            weight[rootX] = weight[y] * value / weight[x];
        }

        // 路径压缩，在find的过程中就把路径压缩了
        public int find(int i) {
            if (i != parent[i]) {
                int origin = parent[i];
                parent[i] = find(parent[i]);
                weight[i] *= weight[origin];
            }
            return parent[i];
        }

        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0d;
            }
        }
    }

    /* 207. 课程表 */

    // 自己的方法，主要是查找入度为0的队列耗时大，为O(V^2 + E)
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 判断是否为一个有向无环图：每次找入度为0的节点遍历，并更新入度出度
        int[] in = new int[numCourses];
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        // 构建图，确定入度
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre_course = prerequisite[1];
            graph[pre_course].add(course);
            in[course]++;
        }
        // 访问入度为0的节点
        boolean[] isVisited = new boolean[numCourses];
        int visitNum = 0;
        while (true) {
            // 如果都访问了，返回
            if (visitNum == numCourses)
                return true;
            // 找入度为0的节点
            int node = -1;
            for (int i = 0; i < numCourses; i++) {
                if (!isVisited[i] && in[i] == 0) {
                    node = i;
                    break;
                }
            }
            // 如果没有入度为0的，返回结果
            if (node == -1)
                return false;
            // 处理这个节点
            isVisited[node] = true;
            visitNum++;
            // 把他关联的节点in值减一
            for (int i = 0; i < graph[node].size(); i++) {
                in[graph[node].get(i)]--;
            }
        }
    }

    // 用队列优化，实现O(E + V)。逻辑是：不用每次都遍历一遍，第一次找到的存起来，第二次找到的一定在第一次找到的节点之后！
    public boolean canFinish_optimized(int numCourses, int[][] prerequisites) {
        // 入度数组
        int[] inDegree = new int[numCourses];
        // 图的邻接表表示
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        // 构建图和入度
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre_course = prerequisite[1];
            graph[pre_course].add(course);
            inDegree[course]++;
        }
        // 队列存储入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 已访问的节点数量
        int visitedCount = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visitedCount++;
            // 遍历该节点的所有出边，降低相应节点的入度
            for (int neighbor : graph[node]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        // 如果访问了所有节点，则说明可以完成所有课程
        return visitedCount == numCourses;
    }

    /* 210. 课程表 II */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        int[] inDegree = new int[numCourses];
        int[] ans = new int[numCourses];
        int count = 0;
        Deque<Integer> nextZeroInDegree = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];
            inDegree[course]++;
            graph[preCourse].add(course);
        }
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                nextZeroInDegree.addLast(i);
        }
        while (!nextZeroInDegree.isEmpty()) {
            int zeroInDegree = nextZeroInDegree.pollFirst();
            ans[count++] = zeroInDegree;
            for (int nextCourse : graph[zeroInDegree]) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0)
                    nextZeroInDegree.addLast(nextCourse);
            }
        }
        return count == numCourses ? ans : new int[0];
    }

    public static void main(String[] args) {
        Classic150_graph c = new Classic150_graph();
    }
}
